package me.mingshan.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/description/
 * <p>
 * 给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。
 * <p>
 * 其中，克隆树 cloned 是原始树 original 的一个 副本 。
 * <p>
 * 请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。
 * <p>
 * <p>
 * <p>
 * 注意：你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。
 *
 * @author hanjuntao
 * @date 2025/10/2 0002
 */
public class L_1379_找出克隆二叉树的相同节点 {

    public static void main(String[] args) {


    }

    /**
     * 思路：
     * 直接遍历cloned树，找到与target相同的节点，返回该节点
     *
     * @param original
     * @param cloned
     * @param target
     * @return
     */
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        List<TreeNode> result = new ArrayList<>();
        dfs(cloned, target, result);

        if (result.size() > 0) {
            return result.get(0);
        }
        return null;
    }

    private void dfs(TreeNode cloned, TreeNode target, List<TreeNode> result) {
        if (cloned == null) {
            return;
        }

        if (cloned.val == target.val) {
            result.add(cloned);
            return;
        }

        dfs(cloned.left, target, result);
        dfs(cloned.right, target, result);
    }
}
